// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
public class Code01_LowestCommonAncestor {
    // 不提交这个类，这个内部类用于表示二叉树的节点
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    // 提交如下的方法，用于寻找二叉树中两个节点的最近公共祖先
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果当前节点root为空，或者当前节点就是p或者q中的一个
        // 那么直接返回当前节点root。这是递归的基本情况。
        // 因为如果当前节点为空，那么在这个子树中肯定找不到公共祖先，直接返回null（这里的null就是root）
        // 如果当前节点是p或者q，那么这个节点有可能是公共祖先（如果另一个节点在这个节点的子树中），所以直接返回
        if (root == null || root == p || root == q) {
            return root;
        }

        // 递归地在左子树中寻找p和q的最近公共祖先，记为l
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        // 递归地在右子树中寻找p和q的最近公共祖先，记为r
        TreeNode r = lowestCommonAncestor(root.right, p, q);

        // 如果l和r都不为空，这意味着p和q分别在当前节点root的左右子树中
        // 所以root就是它们的最近公共祖先，返回root
        if (l!= null && r!= null) {
            return root;
        }

        // 如果l和r都为空，说明在当前子树（包括左子树和右子树）中没有找到p和q
        // 那么在这个子树中就不存在公共祖先，返回null
        if (l == null && r == null) {
            return null;
        }

        // 如果l和r其中一个为空，一个不为空，那么最近公共祖先就是不为空的那个节点
        // 这意味着p和q都在不为空的那个子树中（如果不为空的是l，说明p和q都在左子树中；如果不为空的是r，说明p和q都在右子树中）
        // 所以返回l或者r（取决于哪个不为空）
        return l!= null? l : r;
    }
}